#include "hw5.h"
#include <iostream>
#include <algorithm> //包含许多内置函数，如排序、倒置、交换等函数
using namespace std; //命名空间，防止重名给程序带来各种隐患，使用cin，cout，map，set，vector，queue时都要使用

vector<btree> vp;
vector<btree> vq;

/****把除了p和根节点以外的路径结点按逆序放进数组中****/
bool in_p(btree n, btree rt) // n是寻找的结点，t是根节点，v是存放祖先结点的容器
{
    if (n == rt->lc || n == rt->rc)
    {
        return true;
    }
    if (rt->lc != NULL && in_p(n, rt->lc) == true)
    {
        vp.push_back(rt->lc);
        return true;
    }
    else if (rt->rc != NULL && in_p(n, rt->rc) == true)
    {
        vp.push_back(rt->rc);
        return true;
    }
    else
    {
        return false;
    }
}
/****把除了p和根节点以外的路径结点按逆序放进数组中****/

/****把除了q和根节点以外的路径结点按逆序放进数组中****/
bool in_q(btree n, btree rt) // n是寻找的结点，t是根节点，v是存放祖先结点的容器
{
    if (n == rt->lc || n == rt->rc)
    {
        return true;
    }
    if (rt->lc != NULL && in_q(n, rt->lc) == true)
    {
        vq.push_back(rt->lc);
        return true;
    }
    else if (rt->rc != NULL && in_q(n, rt->rc) == true)
    {
        vq.push_back(rt->rc);
        return true;
    }
    else
    {
        return false;
    }
}
/****把除了q和根节点以外的路径结点按逆序放进数组中****/

/*****把rt结点补到相应的数组中（p和q不放入），并输出p和q到rt各自的路径结点*****/
bool route(btree p, btree q, btree rt)
{

    if (p == NULL)
    {
        cout << " p结点：NULL\n";
    }
    else
    {
        cout << " p结点：" << p->data << "\n";
    }

    if (q == NULL)
    {
        cout << " q结点：NULL\n";
    }
    else
    {
        cout << " q结点：" << q->data << "\n";
    }

    if (p == NULL)
    {
        cout << "rt结点：NULL\n";
    }
    else
    {
        cout << "rt结点：" << rt->data << "\n";
    }

    if (p == NULL || q == NULL || rt == NULL)
    {
        cout << "rt结点、p结点和q结点均禁止为空！\n";
        return false;
    }

    if (p == rt || q == rt)
    {
        cout << "p结点和q结点均不可以与rt结点重合！\n";
        return false;
    }

    in_p(p, rt); //不可以把vector变量作为形参，否则函数调用结束后无法保留结果！
    vp.push_back(rt);

    cout << "从p结点到rt结点的路径：" << p->data;
    for (btree n : vp)
    {
        cout << ' ' << n->data;
    }
    cout << "\n";

    in_q(q, rt); //不可以把vector变量作为形参，否则函数调用结束后无法保留结果！
    vq.push_back(rt);

    cout << "从q结点到rt结点的路径：" << q->data;
    for (btree n : vq)
    {
        cout << ' ' << n->data;
    }
    cout << "\n";
    return true;
}
/*****把rt结点补到相应的数组中（p和q不放入），并输出p和q到rt各自的路径结点*****/

/*****找到离p和q最接近的祖先结点，并清空vp和vq*****/
btree first_same()
{
    btree temp = NULL;
    for (int i = 0; i < vp.size(); i++)
    {
        for (int j = 0; j < vp.size(); j++)
        {
            if (vp[i] == vq[j])
            {
                temp = vp[i];
                break;
            }
        }
        if (temp != NULL)
        {
            break;
        }
    }
    vp.clear();
    vq.clear();
    return temp;
}
/*****找到离p和q最接近的祖先结点，并清空vp和vq*****/

/*****主函数*****/
int main()
{
    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));
    t9 = (btree)malloc(sizeof(btnode));

    /***定义题目要求的3个指针变量***/
    btree p = NULL;
    btree q = NULL;
    btree rt = NULL;
    /***定义题目要求的3个指针变量***/

    /***空结点***/
    cout << "*****空二叉树*****\n";
    print_t(rt);
    if (route(p, q, rt) == true)
    {
        cout << "距离p和q最近的祖先结点：" << first_same()->data << "\n";
    }
    cout << "*****空二叉树*****\n\n\n\n";
    /***空结点***/

    /***第1棵非空二叉树***/
    cout << "/*****第1棵非空二叉树*****/\n";
    t_init();
    t1->lc = t2;
    t2->lc = t3;
    t2->rc = t4;
    t3->lc = t5;
    t4->rc = t7;
    t5->rc = t6;
    t7->lc = t8;
    t7->rc = t9;

    p = t1;
    q = t9;
    rt = t1;

    print_t(rt);
    if (route(p, q, rt) == true)
    {
        cout << "距离p和q最近的祖先结点：" << first_same()->data << "\n";
    }
    cout << "/*****第1棵非空二叉树*****/\n\n\n\n";
    /***第1棵非空二叉树***/

    /***第2棵非空二叉树***/
    cout << "/*****第2棵非空二叉树*****/\n";
    t_init();
    t1->lc = t2;
    t2->lc = t3;
    t2->rc = t4;
    t3->lc = t5;
    t4->rc = t7;
    t5->rc = t6;
    t7->lc = t8;
    t7->rc = t9;

    p = t8;
    q = t9;
    rt = t1;

    print_t(rt);
    if (route(p, q, rt) == true)
    {
        cout << "距离p和q最近的祖先结点：" << first_same()->data << "\n";
    }
    cout << "/*****第2棵非空二叉树*****/\n\n\n\n";
    /***第2棵非空二叉树***/

    /***第3棵非空二叉树***/
    cout << "/*****第3棵非空二叉树*****/\n";
    t_init();
    t1->lc = t2;
    t2->lc = t3;
    t3->lc = t4;
    t4->lc = t5;
    t1->rc = t6;
    t6->rc = t7;
    t7->rc = t8;
    t8->rc = t9;

    p = t5;
    q = t9;
    rt = t1;

    print_t(rt);
    if (route(p, q, rt) == true)
    {
        cout << "距离p和q最近的祖先结点：" << first_same()->data << "\n";
    }
    cout << "/*****第3棵非空二叉树*****/\n\n\n\n";
    /***第3棵非空二叉树***/

    /***第4棵非空二叉树***/
    cout << "/*****第4棵非空二叉树*****/\n";
    t_init();
    t1->lc = t2;
    t2->rc = t3;
    t3->lc = t4;
    t3->rc = t5;
    t4->lc = t6;
    t4->rc = t7;
    t6->rc = t8;
    t7->lc = t9;

    p = t8;
    q = t4;
    rt = t1;

    print_t(rt);
    if (route(p, q, rt) == true)
    {
        cout << "距离p和q最近的祖先结点：" << first_same()->data << "\n";
    }
    cout << "/*****第4棵非空二叉树*****/\n\n\n\n";
    /***第4棵非空二叉树***/

    system("pause");
}
/*****主函数*****/